package com.ocean.binarysearch;

/**
 * <Description> <br>
 *
 * @author linmiaolai@sanyygp.com<br>
 * @version 1.0<br>
 * @date 2023/02/03 <br>
 */
public class BinarySearchII {
    public static void main(String[] args) {
        int[] nums = {1, 3, 4, 5, 6, 8, 8, 8, 12, 18};
        System.out.println(new BinarySearchII().searchLastSmall(nums, nums.length, 11));
    }

    /**
     * 找到第一个相等的
     *
     * @param nums
     * @param n
     * @param value
     * @return
     */
    public int searchFirst(int[] nums, int n, int value) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (nums[mid] > value) {
                high = mid - 1;
            } else if (nums[mid] < value) {
                low = mid + 1;
            } else {
                if (mid == 0 || nums[mid - 1] != value) {
                    return mid;
                }
                high = mid - 1;
            }
        }
        return -1;
    }

    /**
     * 找到最后一个相等的
     *
     * @param nums
     * @param n
     * @param value
     * @return
     */
    public int searchLast(int[] nums, int n, int value) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (nums[mid] > value) {
                high = mid - 1;
            } else if (nums[mid] < value) {
                low = mid + 1;
            } else {
                if (mid == n - 1 || nums[mid + 1] != value) {
                    return mid;
                }
                low = mid + 1;
            }
        }
        return -1;
    }

    /**
     * 找到第一个大于等于
     *
     * @param nums
     * @param n
     * @param value
     * @return
     */
    public int searchFirstBig(int[] nums, int n, int value) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (nums[mid] > value) {
                // 判断是否是第一个大
                if (mid == 0 || nums[mid - 1] <= value) {
                    return mid;
                }
                high = mid - 1;
            } else {
                low = mid + 1;
            }
        }
        return -1;
    }

    // 查找最后一个小于等于
    public int searchLastSmall(int[] nums, int n, int value) {
        int low = 0;
        int high = n - 1;
        while (low <= high) {
            int mid = low + ((high - low) >> 1);
            if (nums[mid] <= value) {
                // 判断是否是最后一个小
                if (mid == n - 1 || nums[mid + 1] > value) {
                    return mid;
                } else {
                    low = mid + 1;
                }
            } else {
                high = mid - 1;
            }
        }
        return -1;
    }
}
